/*
day239
2020.4.23
*/
#include<vector>
#include<algorithm>
#include<map>
using namespace std;

struct TreeNode {
   int val;
   TreeNode *left;
   TreeNode *right;    
   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
	struct Node{
		int Y;
		int val;
	};
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
		map<int,vector<Node>> m;
		record(root,m,0,0);
		vector<vector<int>> res;
		
		for(auto &pair:m)
		{
			vector<Node> vec=pair.second; 
			sort(vec.begin(),vec.end(),isshorter);
			vector<int> tem;
			for(auto &node:vec)
			{
				tem.push_back(node.val);
			}
			res.push_back(tem);
		}
		
		return res;
    }
    
    bool isshorter(const vector<int> &node1,const vector<int> &node2)
    {
		return node1[0]<node2[0] || (node1[0]==node2[0] && node1[1]<node2[1]);
	}
    
    void record(TreeNode *root,map<int,vector<Node>> &m,int x,int y)
    {
    	if(!root)
    	{
    		return ;
		}
		
		Node tem;
		tem.Y=y;
		tem.val=root->val;
		m[x].push_back(tem);
		
		record(root->left,m,x-1,y-1); 
		record(root->left,m,x+1,y-1);
	}
    
};
